/*-------------------------------------------------------------------------
 *
 * network_selfuncs.c
 *	  对 inet/cidr 运算符的选择性估算函数
 *
 * 本模块提供子网包含和重叠的运算符的估算器。
 * 估算基于空值比例、最常见值和 inet/cidr 列的直方图。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/utils/adt/network_selfuncs.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <math.h>

#include "access/htup_details.h"
#include "catalog/pg_operator.h"
#include "catalog/pg_statistic.h"
#include "utils/builtins.h"
#include "utils/inet.h"
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"


/* inet 重叠运算符的默认选择性 */
#define DEFAULT_OVERLAP_SEL 0.01

/* 各种包含运算符的默认选择性 */
#define DEFAULT_INCLUSION_SEL 0.005

/* 指定运算符的默认选择性 */
#define DEFAULT_SEL(operator) \
	((operator) == OID_INET_OVERLAP_OP ? \
	 DEFAULT_OVERLAP_SEL : DEFAULT_INCLUSION_SEL)

/* 在连接选择性计算中考虑的最大项数 */
#define MAX_CONSIDERED_ELEMS 1024

static Selectivity fc_networkjoinsel_inner(Oid fc_operator,
										VariableStatData *fc_vardata1, VariableStatData *fc_vardata2);
static Selectivity fc_networkjoinsel_semi(Oid fc_operator,
									   VariableStatData *fc_vardata1, VariableStatData *fc_vardata2);
static Selectivity fc_mcv_population(float4 *fc_mcv_numbers, int fc_mcv_nvalues);
static Selectivity fc_inet_hist_value_sel(Datum *fc_values, int fc_nvalues,
									   Datum fc_constvalue, int fc_opr_codenum);
static Selectivity fc_inet_mcv_join_sel(Datum *fc_mcv1_values,
									 float4 *fc_mcv1_numbers, int fc_mcv1_nvalues, Datum *fc_mcv2_values,
									 float4 *fc_mcv2_numbers, int fc_mcv2_nvalues, Oid fc_operator);
static Selectivity fc_inet_mcv_hist_sel(Datum *fc_mcv_values, float4 *fc_mcv_numbers,
									 int fc_mcv_nvalues, Datum *fc_hist_values, int fc_hist_nvalues,
									 int fc_opr_codenum);
static Selectivity fc_inet_hist_inclusion_join_sel(Datum *fc_hist1_values,
												int fc_hist1_nvalues,
												Datum *fc_hist2_values, int fc_hist2_nvalues,
												int fc_opr_codenum);
static Selectivity fc_inet_semi_join_sel(Datum fc_lhs_value,
									  bool fc_mcv_exists, Datum *fc_mcv_values, int fc_mcv_nvalues,
									  bool fc_hist_exists, Datum *fc_hist_values, int fc_hist_nvalues,
									  double fc_hist_weight,
									  FmgrInfo *fc_proc, int fc_opr_codenum);
static int	fc_inet_opr_codenum(Oid fc_operator);
static int	fc_inet_inclusion_cmp(inet *fc_left, inet *fc_right, int fc_opr_codenum);
static int	fc_inet_masklen_inclusion_cmp(inet *fc_left, inet *fc_right,
									   int fc_opr_codenum);
static int	fc_inet_hist_match_divider(inet *fc_boundary, inet *fc_query,
									int fc_opr_codenum);

/*
 * 子网包含/重叠运算符的选择性估计
 */
Datum networksel(PG_FUNCTION_ARGS)
{
	PlannerInfo *fc_root = (PlannerInfo *) PG_GETARG_POINTER(0);
	Oid			fc_operator = PG_GETARG_OID(1);
	List	   *fc_args = (List *) PG_GETARG_POINTER(2);
	int			fc_varRelid = PG_GETARG_INT32(3);
	VariableStatData fc_vardata;
	Node	   *fc_other;
	bool		fc_varonleft;
	Selectivity fc_selec,
				fc_mcv_selec,
				fc_non_mcv_selec;
	Datum		fc_constvalue;
	Form_pg_statistic fc_stats;
	AttStatsSlot fc_hslot;
	double		fc_sumcommon,
				fc_nullfrac;
	FmgrInfo	fc_proc;

	/*
	 * 如果表达式不是 (变量 op 某个值) 或 (某个值 op
	 * 变量)，那么返回默认估计。
	 */
	if (!get_restriction_variable(fc_root, fc_args, fc_varRelid,
								  &fc_vardata, &fc_other, &fc_varonleft))
		PG_RETURN_FLOAT8(DEFAULT_SEL(fc_operator));

	/*
	 * 如果 something 也不是常量，就无法做任何有用的事情。
	 */
	if (!IsA(fc_other, Const))
	{
		ReleaseVariableStats(fc_vardata);
		PG_RETURN_FLOAT8(DEFAULT_SEL(fc_operator));
	}

	/* 这里处理的所有运算符都是严格的。 */
	if (((Const *) fc_other)->constisnull)
	{
		ReleaseVariableStats(fc_vardata);
		PG_RETURN_FLOAT8(0.0);
	}
	fc_constvalue = ((Const *) fc_other)->constvalue;

	/* 否则，我们需要统计信息以产生非默认估计。 */
	if (!HeapTupleIsValid(fc_vardata.statsTuple))
	{
		ReleaseVariableStats(fc_vardata);
		PG_RETURN_FLOAT8(DEFAULT_SEL(fc_operator));
	}

	fc_stats = (Form_pg_statistic) GETSTRUCT(fc_vardata.statsTuple);
	fc_nullfrac = fc_stats->stanullfrac;

	/*
	 * 如果我们有最常见值信息，请将满足 MCV OP CONST
	 * 的 MCV 条目的分数相加。这些分数直接
	 * 影响结果的选择性。还要相加由 MCV 条目表示的
	 * 总分数。
	 */
	fmgr_info(get_opcode(fc_operator), &fc_proc);
	fc_mcv_selec = mcv_selectivity(&fc_vardata, &fc_proc, InvalidOid,
								fc_constvalue, fc_varonleft,
								&fc_sumcommon);

	/*
	 * 如果我们有直方图，使用它来估计满足该子句的
	 * 非 MCV 人口的比例。如果没有，则对该人口应用
	 * 默认选择性。
	 */
	if (get_attstatsslot(&fc_hslot, fc_vardata.statsTuple,
						 STATISTIC_KIND_HISTOGRAM, InvalidOid,
						 ATTSTATSSLOT_VALUES))
	{
		int			fc_opr_codenum = fc_inet_opr_codenum(fc_operator);

		/* 如有需要，则调换顺序，以便我们可以将直方图视为在左侧 */
		if (!fc_varonleft)
			fc_opr_codenum = -fc_opr_codenum;
		fc_non_mcv_selec = fc_inet_hist_value_sel(fc_hslot.values, fc_hslot.nvalues,
											fc_constvalue, fc_opr_codenum);

		free_attstatsslot(&fc_hslot);
	}
	else
		fc_non_mcv_selec = DEFAULT_SEL(fc_operator);

	/* 结合 MCV 和非 MCV 人口的选择性 */
	fc_selec = fc_mcv_selec + (1.0 - fc_nullfrac - fc_sumcommon) * fc_non_mcv_selec;

	/* 结果应该在范围内，但确保... */
	CLAMP_PROBABILITY(fc_selec);

	ReleaseVariableStats(fc_vardata);

	PG_RETURN_FLOAT8(fc_selec);
}

/*
 * 子网包含/重叠运算符的连接选择性估计
 *
 * 此函数的结构与 selfuncs.c 中的 eqjoinsel() 相同。
 *
 * 在 networkjoinsel 及其子例程中，我们面临性能问题，
 * 因为要处理的工作量在 MCV 和直方图数组的长度
 * 上是 O(N^2)。为了避免在设置了大统计目标时运行时间失控，
 * 我们任意限制考虑的值的数量为 1024（MAX_CONSIDERED_ELEMS）。
 * 对于 MCV 数组，这很好：最多考虑前 N 个元素。
 * （由于 MCV 按频率递减排序，这正确地得到前 N 个 MCV。）
 * 对于直方图数组，我们进行抽样；即只考虑每第 k 个
 * 元素，其中 k 的选择使得考虑的元素不超过 MAX_CONSIDERED_ELEMS。
 * 这仍然应该给我们提供非 MCV 人口的良好随机样本。
 * 抽样是在迭代直方图数组的循环中即时进行的。
 */
Datum networkjoinsel(PG_FUNCTION_ARGS)
{
	PlannerInfo *fc_root = (PlannerInfo *) PG_GETARG_POINTER(0);
	Oid			fc_operator = PG_GETARG_OID(1);
	List	   *fc_args = (List *) PG_GETARG_POINTER(2);
#ifdef NOT_USED
	JoinType	fc_jointype = (JoinType) PG_GETARG_INT16(3);
#endif
	SpecialJoinInfo *fc_sjinfo = (SpecialJoinInfo *) PG_GETARG_POINTER(4);
	double		fc_selec;
	VariableStatData fc_vardata1;
	VariableStatData fc_vardata2;
	bool		fc_join_is_reversed;

	get_join_variables(fc_root, fc_args, fc_sjinfo,
					   &fc_vardata1, &fc_vardata2, &fc_join_is_reversed);

	switch (fc_sjinfo->jointype)
	{
		case JOIN_INNER:
		case JOIN_LEFT:
		case JOIN_FULL:

			/*
			 * 左/全连接的选择性与内部连接不完全相同，
			 * 但我们忽略这种差异，正如 eqjoinsel 所做的那样。
			 */
			fc_selec = fc_networkjoinsel_inner(fc_operator, &fc_vardata1, &fc_vardata2);
			break;
		case JOIN_SEMI:
		case JOIN_ANTI:
			/* 在这里，重要的是我们将外部变量传递到左侧。 */
			if (!fc_join_is_reversed)
				fc_selec = fc_networkjoinsel_semi(fc_operator, &fc_vardata1, &fc_vardata2);
			else
				fc_selec = fc_networkjoinsel_semi(get_commutator(fc_operator),
											&fc_vardata2, &fc_vardata1);
			break;
		default:
			/* 此处不期望其他值 */
			elog(ERROR, "unrecognized join type: %d",
				 (int) fc_sjinfo->jointype);
			fc_selec = 0;			/* 保持编译器安静 */
			break;
	}

	ReleaseVariableStats(fc_vardata1);
	ReleaseVariableStats(fc_vardata2);

	CLAMP_PROBABILITY(fc_selec);

	PG_RETURN_FLOAT8((float8) fc_selec);
}


static Selectivity fc_networkjoinsel_inner(Oid fc_operator,
					 VariableStatData *fc_vardata1, VariableStatData *fc_vardata2)
{
	Form_pg_statistic fc_stats;
	double		fc_nullfrac1 = 0.0,
				fc_nullfrac2 = 0.0;
	Selectivity fc_selec = 0.0,
				fc_sumcommon1 = 0.0,
				fc_sumcommon2 = 0.0;
	bool		fc_mcv1_exists = false,
				fc_mcv2_exists = false,
				fc_hist1_exists = false,
				fc_hist2_exists = false;
	int			fc_opr_codenum;
	int			fc_mcv1_length = 0,
				fc_mcv2_length = 0;
	AttStatsSlot fc_mcv1_slot;
	AttStatsSlot fc_mcv2_slot;
	AttStatsSlot fc_hist1_slot;
	AttStatsSlot fc_hist2_slot;

	if (HeapTupleIsValid(fc_vardata1->statsTuple))
	{
		fc_stats = (Form_pg_statistic) GETSTRUCT(fc_vardata1->statsTuple);
		fc_nullfrac1 = fc_stats->stanullfrac;

		fc_mcv1_exists = get_attstatsslot(&fc_mcv1_slot, fc_vardata1->statsTuple,
									   STATISTIC_KIND_MCV, InvalidOid,
									   ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS);
		fc_hist1_exists = get_attstatsslot(&fc_hist1_slot, fc_vardata1->statsTuple,
										STATISTIC_KIND_HISTOGRAM, InvalidOid,
										ATTSTATSSLOT_VALUES);
		/* 随意限制考虑的MCV数量 */
		fc_mcv1_length = Min(fc_mcv1_slot.nvalues, MAX_CONSIDERED_ELEMS);
		if (fc_mcv1_exists)
			fc_sumcommon1 = fc_mcv_population(fc_mcv1_slot.numbers, fc_mcv1_length);
	}
	else
	{
		memset(&fc_mcv1_slot, 0, sizeof(fc_mcv1_slot));
		memset(&fc_hist1_slot, 0, sizeof(fc_hist1_slot));
	}

	if (HeapTupleIsValid(fc_vardata2->statsTuple))
	{
		fc_stats = (Form_pg_statistic) GETSTRUCT(fc_vardata2->statsTuple);
		fc_nullfrac2 = fc_stats->stanullfrac;

		fc_mcv2_exists = get_attstatsslot(&fc_mcv2_slot, fc_vardata2->statsTuple,
									   STATISTIC_KIND_MCV, InvalidOid,
									   ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS);
		fc_hist2_exists = get_attstatsslot(&fc_hist2_slot, fc_vardata2->statsTuple,
										STATISTIC_KIND_HISTOGRAM, InvalidOid,
										ATTSTATSSLOT_VALUES);
		/* 随意限制考虑的MCV数量 */
		fc_mcv2_length = Min(fc_mcv2_slot.nvalues, MAX_CONSIDERED_ELEMS);
		if (fc_mcv2_exists)
			fc_sumcommon2 = fc_mcv_population(fc_mcv2_slot.numbers, fc_mcv2_length);
	}
	else
	{
		memset(&fc_mcv2_slot, 0, sizeof(fc_mcv2_slot));
		memset(&fc_hist2_slot, 0, sizeof(fc_hist2_slot));
	}

	fc_opr_codenum = fc_inet_opr_codenum(fc_operator);

	/*
	 * 计算MCV与MCV匹配的选择性。
	 */
	if (fc_mcv1_exists && fc_mcv2_exists)
		fc_selec += fc_inet_mcv_join_sel(fc_mcv1_slot.values, fc_mcv1_slot.numbers,
								   fc_mcv1_length,
								   fc_mcv2_slot.values, fc_mcv2_slot.numbers,
								   fc_mcv2_length,
								   fc_operator);

	/*
	 * 添加MCV与直方图匹配的选择性，根据
	 * 直方图表示的人群比例进行缩放。注意
	 * 第二种情况需要交互操作符。
	 */
	if (fc_mcv1_exists && fc_hist2_exists)
		fc_selec += (1.0 - fc_nullfrac2 - fc_sumcommon2) *
			fc_inet_mcv_hist_sel(fc_mcv1_slot.values, fc_mcv1_slot.numbers, fc_mcv1_length,
							  fc_hist2_slot.values, fc_hist2_slot.nvalues,
							  fc_opr_codenum);
	if (fc_mcv2_exists && fc_hist1_exists)
		fc_selec += (1.0 - fc_nullfrac1 - fc_sumcommon1) *
			fc_inet_mcv_hist_sel(fc_mcv2_slot.values, fc_mcv2_slot.numbers, fc_mcv2_length,
							  fc_hist1_slot.values, fc_hist1_slot.nvalues,
							  -fc_opr_codenum);

	/*
	 * 添加直方图与直方图匹配的选择性，同样进行适当缩放。
	 */
	if (fc_hist1_exists && fc_hist2_exists)
		fc_selec += (1.0 - fc_nullfrac1 - fc_sumcommon1) *
			(1.0 - fc_nullfrac2 - fc_sumcommon2) *
			fc_inet_hist_inclusion_join_sel(fc_hist1_slot.values, fc_hist1_slot.nvalues,
										 fc_hist2_slot.values, fc_hist2_slot.nvalues,
										 fc_opr_codenum);

	/*
	 * 如果有用的统计信息不可用，则使用默认估计。
	 * 不过，如果已知可以应用空分数。
	 */
	if ((!fc_mcv1_exists && !fc_hist1_exists) || (!fc_mcv2_exists && !fc_hist2_exists))
		fc_selec = (1.0 - fc_nullfrac1) * (1.0 - fc_nullfrac2) * DEFAULT_SEL(fc_operator);

	/* 释放统计信息。 */
	free_attstatsslot(&fc_mcv1_slot);
	free_attstatsslot(&fc_mcv2_slot);
	free_attstatsslot(&fc_hist1_slot);
	free_attstatsslot(&fc_hist2_slot);

	return fc_selec;
}

/*
 * 半连接选择性估计用于子网包含/重叠操作符
 *
 * 计算MCV与MCV、MCV与直方图、直方图与MCV，以及直方图与
 * 直方图在半连接/反连接情况下的选择性。
 */
static Selectivity fc_networkjoinsel_semi(Oid fc_operator,
					VariableStatData *fc_vardata1, VariableStatData *fc_vardata2)
{
	Form_pg_statistic fc_stats;
	Selectivity fc_selec = 0.0,
				fc_sumcommon1 = 0.0,
				fc_sumcommon2 = 0.0;
	double		fc_nullfrac1 = 0.0,
				fc_nullfrac2 = 0.0,
				fc_hist2_weight = 0.0;
	bool		fc_mcv1_exists = false,
				fc_mcv2_exists = false,
				fc_hist1_exists = false,
				fc_hist2_exists = false;
	int			fc_opr_codenum;
	FmgrInfo	fc_proc;
	int			fc_i,
				fc_mcv1_length = 0,
				fc_mcv2_length = 0;
	AttStatsSlot fc_mcv1_slot;
	AttStatsSlot fc_mcv2_slot;
	AttStatsSlot fc_hist1_slot;
	AttStatsSlot fc_hist2_slot;

	if (HeapTupleIsValid(fc_vardata1->statsTuple))
	{
		fc_stats = (Form_pg_statistic) GETSTRUCT(fc_vardata1->statsTuple);
		fc_nullfrac1 = fc_stats->stanullfrac;

		fc_mcv1_exists = get_attstatsslot(&fc_mcv1_slot, fc_vardata1->statsTuple,
									   STATISTIC_KIND_MCV, InvalidOid,
									   ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS);
		fc_hist1_exists = get_attstatsslot(&fc_hist1_slot, fc_vardata1->statsTuple,
										STATISTIC_KIND_HISTOGRAM, InvalidOid,
										ATTSTATSSLOT_VALUES);
		/* 随意限制考虑的MCV数量 */
		fc_mcv1_length = Min(fc_mcv1_slot.nvalues, MAX_CONSIDERED_ELEMS);
		if (fc_mcv1_exists)
			fc_sumcommon1 = fc_mcv_population(fc_mcv1_slot.numbers, fc_mcv1_length);
	}
	else
	{
		memset(&fc_mcv1_slot, 0, sizeof(fc_mcv1_slot));
		memset(&fc_hist1_slot, 0, sizeof(fc_hist1_slot));
	}

	if (HeapTupleIsValid(fc_vardata2->statsTuple))
	{
		fc_stats = (Form_pg_statistic) GETSTRUCT(fc_vardata2->statsTuple);
		fc_nullfrac2 = fc_stats->stanullfrac;

		fc_mcv2_exists = get_attstatsslot(&fc_mcv2_slot, fc_vardata2->statsTuple,
									   STATISTIC_KIND_MCV, InvalidOid,
									   ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS);
		fc_hist2_exists = get_attstatsslot(&fc_hist2_slot, fc_vardata2->statsTuple,
										STATISTIC_KIND_HISTOGRAM, InvalidOid,
										ATTSTATSSLOT_VALUES);
		/* 随意限制考虑的MCV数量 */
		fc_mcv2_length = Min(fc_mcv2_slot.nvalues, MAX_CONSIDERED_ELEMS);
		if (fc_mcv2_exists)
			fc_sumcommon2 = fc_mcv_population(fc_mcv2_slot.numbers, fc_mcv2_length);
	}
	else
	{
		memset(&fc_mcv2_slot, 0, sizeof(fc_mcv2_slot));
		memset(&fc_hist2_slot, 0, sizeof(fc_hist2_slot));
	}

	fc_opr_codenum = fc_inet_opr_codenum(fc_operator);
	fmgr_info(get_opcode(fc_operator), &fc_proc);

	/* 估计由RHS直方图表示的输入行数。 */
	if (fc_hist2_exists && fc_vardata2->rel)
		fc_hist2_weight = (1.0 - fc_nullfrac2 - fc_sumcommon2) * fc_vardata2->rel->rows;

	/*
	 * 考虑LHS MCV列表的每个元素，将其与我们拥有的RHS
	 * 统计信息进行匹配。根据已知的MCV频率进行缩放。
	 */
	if (fc_mcv1_exists && (fc_mcv2_exists || fc_hist2_exists))
	{
		for (fc_i = 0; fc_i < fc_mcv1_length; fc_i++)
		{
			fc_selec += fc_mcv1_slot.numbers[fc_i] *
				fc_inet_semi_join_sel(fc_mcv1_slot.values[fc_i],
								   fc_mcv2_exists, fc_mcv2_slot.values, fc_mcv2_length,
								   fc_hist2_exists,
								   fc_hist2_slot.values, fc_hist2_slot.nvalues,
								   fc_hist2_weight,
								   &fc_proc, fc_opr_codenum);
		}
	}

	/*
	 * 考虑LHS直方图中的每个元素，除了第一个和
	 * 最后一个元素，我们将其排除，因为它们是异常值，
	 * 因此不太具有代表性。假设每个
	 * 这样的直方图元素代表LHS直方图
	 * 人口的相等份额进行缩放（这有点不准确，因为它的桶中的成员可能
	 * 不会在连接子句方面表现得一样，但更难
	 * 有更好的处理）。
	 *
	 * 如果直方图元素过多，进行减缩以限制运行时间。
	 */
	if (fc_hist1_exists && fc_hist1_slot.nvalues > 2 && (fc_mcv2_exists || fc_hist2_exists))
	{
		double		fc_hist_selec_sum = 0.0;
		int			fc_k,
					fc_n;

		fc_k = (fc_hist1_slot.nvalues - 3) / MAX_CONSIDERED_ELEMS + 1;

		fc_n = 0;
		for (fc_i = 1; fc_i < fc_hist1_slot.nvalues - 1; fc_i += fc_k)
		{
			fc_hist_selec_sum +=
				fc_inet_semi_join_sel(fc_hist1_slot.values[fc_i],
								   fc_mcv2_exists, fc_mcv2_slot.values, fc_mcv2_length,
								   fc_hist2_exists,
								   fc_hist2_slot.values, fc_hist2_slot.nvalues,
								   fc_hist2_weight,
								   &fc_proc, fc_opr_codenum);
			fc_n++;
		}

		fc_selec += (1.0 - fc_nullfrac1 - fc_sumcommon1) * fc_hist_selec_sum / fc_n;
	}

	/*
	 * 如果有用的统计信息不可用，则使用默认估计。
	 * 不过，如果已知可以应用空分数。
	 */
	if ((!fc_mcv1_exists && !fc_hist1_exists) || (!fc_mcv2_exists && !fc_hist2_exists))
		fc_selec = (1.0 - fc_nullfrac1) * (1.0 - fc_nullfrac2) * DEFAULT_SEL(fc_operator);

	/* 释放统计信息。 */
	free_attstatsslot(&fc_mcv1_slot);
	free_attstatsslot(&fc_mcv2_slot);
	free_attstatsslot(&fc_hist1_slot);
	free_attstatsslot(&fc_hist2_slot);

	return fc_selec;
}

/*
 * 计算由MCV列表表示的关系人口的比例。
 */
static Selectivity fc_mcv_population(float4 *fc_mcv_numbers, int fc_mcv_nvalues)
{
	Selectivity fc_sumcommon = 0.0;
	int			fc_i;

	for (fc_i = 0; fc_i < fc_mcv_nvalues; fc_i++)
	{
		fc_sumcommon += fc_mcv_numbers[fc_i];
	}

	return fc_sumcommon;
}

/*
 * Inet直方图与单值选择性估计
 *
 * 估计满足
 * “值 OPR CONST”的直方图人口的比例。(结果需要缩放以反映
 * 直方图所表示的总人口比例。)
 *
 * 该直方图最初用于inet btree比较操作符。
 * 仅网络部分的公共位和网络部分的长度
 *（masklen）对子网包含操作符有趣。幸运的是，
 * btree比较将网络部分视为主要排序键。尽管如此，
 * 网络部分的长度在直方图中的确不太重要。
 * 这会导致数据集在masklen分布不均时出现严重错误。
 * 为减少此问题，使用左右桶的比较。
 *
 * 直方图桶匹配以两种形式计算。如果常量
 * 匹配两个桶端点，则该桶被视为完全匹配。
 * 第二种形式是部分匹配桶；当
 * 常量仅匹配一个端点，或两个端点位于
 * 常量的对立面时，我们承认这一点。
 * （注意，当常量与内部直方图元素匹配时，它获得对
 * 两侧桶的部分匹配的积分，而与直方图端点的匹配只获得
 * 一个部分匹配的积分。这是理想的。）
 *
 * 部分桶匹配中的划分器被想象为决定性位与地址的公共位之间的距离。
 * 它将用作2的幂，因为这是IP网络
 * 包含的自然尺度。这个部分桶匹配划分器的计算是一个经验
 * 公式，可能会随着更多实验而改变。
 *
 * 对于部分匹配，我们尝试为两个
 * 边界计算分隔符。如果边界值的地址族与
 * 常量不匹配或网络部分长度的比较不正确
 * 对于操作符，则该边界的划分器将不予考虑。
 * 如果两个分隔符都是有效的，将使用较大的一个
 * 以减少桶中具有不同masklens的错误。
 * 当两个边界都可以计算出分隔符但它们相距较远时，这种计算是不公平的；
 * 但这并不是一种常见情况，因为边界预计共享大部分其重要的
 * masklens位。如果我们使用最小值而不是最大值，则错误会更大，而我们不知道合理的合并
 * 方式。
 *
 * 对于具有不同地址族的部分匹配桶，
 * 只考虑具有相同地址族的边界。这可能导致这些桶
 * 出现更多错误，如果其边界的masklens也不相同。
 * 但这只会发生在一个桶中，因为只有两种地址族存在。
 * 这似乎是一个比根本不考虑这些桶的更好选择。
 */
static Selectivity fc_inet_hist_value_sel(Datum *fc_values, int fc_nvalues, Datum fc_constvalue,
					int fc_opr_codenum)
{
	Selectivity fc_match = 0.0;
	inet	   *fc_query,
			   *fc_left,
			   *fc_right;
	int			fc_i,
				fc_k,
				fc_n;
	int			fc_left_order,
				fc_right_order,
				fc_left_divider,
				fc_right_divider;

	/* 防止零除错误 */
	if (fc_nvalues <= 1)
		return 0.0;

	/* 如果直方图元素过多，进行减缩以限制运行时间 */
	fc_k = (fc_nvalues - 2) / MAX_CONSIDERED_ELEMS + 1;

	fc_query = DatumGetInetPP(fc_constvalue);

	
/* "left"是当前桶的左边界值... */
	fc_left = DatumGetInetPP(fc_values[0]);
	fc_left_order = fc_inet_inclusion_cmp(fc_left, fc_query, fc_opr_codenum);

	fc_n = 0;
	for (fc_i = fc_k; fc_i < fc_nvalues; fc_i += fc_k)
	{
		/* ... "right"是右边界值 */
		fc_right = DatumGetInetPP(fc_values[fc_i]);
		fc_right_order = fc_inet_inclusion_cmp(fc_right, fc_query, fc_opr_codenum);

		if (fc_left_order == 0 && fc_right_order == 0)
		{
			/* 整个桶匹配，因为两个端点都匹配。 */
			fc_match += 1.0;
		}
		else if ((fc_left_order <= 0 && fc_right_order >= 0) ||
				 (fc_left_order >= 0 && fc_right_order <= 0))
		{
			/* 部分桶匹配。 */
			fc_left_divider = fc_inet_hist_match_divider(fc_left, fc_query, fc_opr_codenum);
			fc_right_divider = fc_inet_hist_match_divider(fc_right, fc_query, fc_opr_codenum);

			if (fc_left_divider >= 0 || fc_right_divider >= 0)
				fc_match += 1.0 / pow(2.0, Max(fc_left_divider, fc_right_divider));
		}

		/* 移动变量。 */
		fc_left = fc_right;
		fc_left_order = fc_right_order;

		/* 计算考虑的桶的数量。 */
		fc_n++;
	}

	return fc_match / fc_n;
}

/*
 * Inet MCV与MCV连接选择性估计
 *
 * 我们简单地将满足该条件的人口比例相加。
 * 结果是精确的，无需进一步缩放。
 */
static Selectivity fc_inet_mcv_join_sel(Datum *fc_mcv1_values, float4 *fc_mcv1_numbers, int fc_mcv1_nvalues,
				  Datum *fc_mcv2_values, float4 *fc_mcv2_numbers, int fc_mcv2_nvalues,
				  Oid fc_operator)
{
	Selectivity fc_selec = 0.0;
	FmgrInfo	fc_proc;
	int			fc_i,
				fc_j;

	fmgr_info(get_opcode(fc_operator), &fc_proc);

	for (fc_i = 0; fc_i < fc_mcv1_nvalues; fc_i++)
	{
		for (fc_j = 0; fc_j < fc_mcv2_nvalues; fc_j++)
			if (DatumGetBool(FunctionCall2(&fc_proc,
										   fc_mcv1_values[fc_i],
										   fc_mcv2_values[fc_j])))
				fc_selec += fc_mcv1_numbers[fc_i] * fc_mcv2_numbers[fc_j];
	}
	return fc_selec;
}

/*
 * Inet MCV与直方图连接选择性估计
 *
 * 对于左侧的每个MCV，估计右侧直方图人口中满足连接条件的比例，并将其相加，按MCV的频率进行缩放。
 * 结果仍然需要根据右侧人口在直方图中所占的比例进行缩放。
 */
static Selectivity fc_inet_mcv_hist_sel(Datum *fc_mcv_values, float4 *fc_mcv_numbers, int fc_mcv_nvalues,
				  Datum *fc_hist_values, int fc_hist_nvalues,
				  int fc_opr_codenum)
{
	Selectivity fc_selec = 0.0;
	int			fc_i;

	/*
	 * 我们将调用inet_hist_value_selec，左侧使用直方图，因此我们
	 * 必须交换算子。
	 */
	fc_opr_codenum = -fc_opr_codenum;

	for (fc_i = 0; fc_i < fc_mcv_nvalues; fc_i++)
	{
		fc_selec += fc_mcv_numbers[fc_i] *
			fc_inet_hist_value_sel(fc_hist_values, fc_hist_nvalues, fc_mcv_values[fc_i],
								fc_opr_codenum);
	}
	return fc_selec;
}

/*
 * Inet直方图与直方图连接选择性估计
 *
 * 在这里，我们取第二个直方图中列出的所有值（除了第一个和最后一个元素，因其可能并不具有代表性而被排除），
 * 并将它们视为该关系的非MCV人口的均匀样本。 对于每一个，我们应用
 * inet_hist_value_selec查看它与第一个直方图匹配的比例。
 *
 * 我们也可以反过来使用算子的对易子。 XXX 是否值得同时进行这两种方式并取平均值？
 * 那样至少可以避免非对易的估计结果。
 */
static Selectivity fc_inet_hist_inclusion_join_sel(Datum *fc_hist1_values, int fc_hist1_nvalues,
							 Datum *fc_hist2_values, int fc_hist2_nvalues,
							 int fc_opr_codenum)
{
	double		fc_match = 0.0;
	int			fc_i,
				fc_k,
				fc_n;

	if (fc_hist2_nvalues <= 2)
		return 0.0;				/* 没有内部直方图元素 */

	/* 如果直方图元素过多，进行减缩以限制运行时间 */
	fc_k = (fc_hist2_nvalues - 3) / MAX_CONSIDERED_ELEMS + 1;

	fc_n = 0;
	for (fc_i = 1; fc_i < fc_hist2_nvalues - 1; fc_i += fc_k)
	{
		fc_match += fc_inet_hist_value_sel(fc_hist1_values, fc_hist1_nvalues,
									 fc_hist2_values[fc_i], fc_opr_codenum);
		fc_n++;
	}

	return fc_match / fc_n;
}

/*
 * Inet半连接选择性估计对于一个值
 *
 * 该函数计算在RHS表中至少有一行满足"lhs_value op column"条件的概率。
 * 它用于半连接估计以检查来自左侧表的样本。
 *
 * 右侧表的MCV和直方图应该作为参数提供，左侧表的lhs_value用于连接。
 * hist_weight是由直方图表示的行总数。
 * 例如，如果表中有1000行，且10%的行在MCV列表中，另外10%是NULL，hist_weight将为800。
 *
 * 首先，将lhs_value与最常见的值进行匹配。如果匹配任意一个，将返回1.0，因为那样肯定会有匹配。
 *
 * 否则，将使用直方图来估计在第二个表中满足该条件的行数。如果估计值大于1.0，将返回1.0，因为
 * 这意味着lhs_value匹配表中的多于一行的可能性更大。如果在0.0到1.0之间，将作为概率返回。
 */
static Selectivity fc_inet_semi_join_sel(Datum fc_lhs_value,
				   bool fc_mcv_exists, Datum *fc_mcv_values, int fc_mcv_nvalues,
				   bool fc_hist_exists, Datum *fc_hist_values, int fc_hist_nvalues,
				   double fc_hist_weight,
				   FmgrInfo *fc_proc, int fc_opr_codenum)
{
	if (fc_mcv_exists)
	{
		int			fc_i;

		for (fc_i = 0; fc_i < fc_mcv_nvalues; fc_i++)
		{
			if (DatumGetBool(FunctionCall2(fc_proc,
										   fc_lhs_value,
										   fc_mcv_values[fc_i])))
				return 1.0;
		}
	}

	if (fc_hist_exists && fc_hist_weight > 0)
	{
		Selectivity fc_hist_selec;

		/* 交换算子，因为我们将lhs_value放在右侧 */
		fc_hist_selec = fc_inet_hist_value_sel(fc_hist_values, fc_hist_nvalues,
										 fc_lhs_value, -fc_opr_codenum);

		if (fc_hist_selec > 0)
			return Min(1.0, fc_hist_weight * fc_hist_selec);
	}

	return 0.0;
}

/*
 * 为子网包含/重叠运算符分配有用的代码号
 *
 * 只有inet_masklen_inclusion_cmp()和inet_hist_match_divider()依赖于这里分配的确切代码；但
 * 本文件中的许多其他地方知道它们可以否定一个代码以获得对易子运算符的代码。
 */
static int fc_inet_opr_codenum(Oid fc_operator)
{
	switch (fc_operator)
	{
		case OID_INET_SUP_OP:
			return -2;
		case OID_INET_SUPEQ_OP:
			return -1;
		case OID_INET_OVERLAP_OP:
			return 0;
		case OID_INET_SUBEQ_OP:
			return 1;
		case OID_INET_SUB_OP:
			return 2;
		default:
			elog(ERROR, "unrecognized operator %u for inet selectivity",
				 fc_operator);
	}
	return 0;					/* 未到达，但保持编译器安静 */
}

/*
 * 子网包含/重叠运算符的比较函数
 *
 * 如果比较对于指定的包含运算符是合适的，返回值将为0。
 * 否则返回值将根据运算符的需要小于或大于0。
 *
 * 比较与inet类型的基本比较函数兼容。有关原始内容，请参见network.c中的network_cmp_internal()。
 * 基本比较运算符使用network_cmp_internal()函数实现。可以使用该函数实现子网包含运算符。
 *
 * 比较首先基于网络部分的共同位，然后基于网络部分的长度（masklen），正如network_cmp_internal()函数中所示。
 * 只有第一部分在此函数中。第二部分被分离到另一个函数以提高可重用性。第二部分和原始network_cmp_internal()之间的区别是
 * 在比较网络部分的长度时考虑了包含运算符。请参阅下面的inet_masklen_inclusion_cmp()函数。
 */
static int fc_inet_inclusion_cmp(inet *fc_left, inet *fc_right, int fc_opr_codenum)
{
	if (ip_family(fc_left) == ip_family(fc_right))
	{
		int			fc_order;

		fc_order = bitncmp(ip_addr(fc_left), ip_addr(fc_right),
						Min(ip_bits(fc_left), ip_bits(fc_right)));
		if (fc_order != 0)
			return fc_order;

		return fc_inet_masklen_inclusion_cmp(fc_left, fc_right, fc_opr_codenum);
	}

	return ip_family(fc_left) - ip_family(fc_right);
}

/*
 * Masklen 比较函数用于子网包含/重叠操作符
 *
 * 比较输入的网络部分长度。如果对于指定的包含操作符比较是可以的，返回值将为 0。
 * 否则，返回值将根据操作符的需要小于或大于 0。
 */
static int fc_inet_masklen_inclusion_cmp(inet *fc_left, inet *fc_right, int fc_opr_codenum)
{
	int			fc_order;

	fc_order = (int) ip_bits(fc_left) - (int) ip_bits(fc_right);

	/*
	 * 如果操作符接受这个掩码长度的组合则返回 0。
	 * 注意， opr_codenum 为零（重叠）将接受所有情况。
	 */
	if ((fc_order > 0 && fc_opr_codenum >= 0) ||
		(fc_order == 0 && fc_opr_codenum >= -1 && fc_opr_codenum <= 1) ||
		(fc_order < 0 && fc_opr_codenum <= 0))
		return 0;

	/*
	 * 否则，对于 sup/supeq 返回负值（从概念上讲，RHS
	 * 需要具有更大的掩码长度，而它没有，这将使其稍后排序），或对于 sub/subeq 返回正值（反之亦然）。
	 */
	return fc_opr_codenum;
}

/*
 * Inet histogram 部分匹配划分器计算
 *
 * 首先，使用子网包含操作符比较网络部分的系列和长度。
 * 如果这些对操作符是可接受的，将使用掩码长度和地址的公共位计算划分器。
 * 如果无法计算，则返回 -1。
 *
 * 有关此的一些理由，请参见 inet_hist_value_sel() 的注释。
 */
static int fc_inet_hist_match_divider(inet *fc_boundary, inet *fc_query, int fc_opr_codenum)
{
	if (ip_family(fc_boundary) == ip_family(fc_query) &&
		fc_inet_masklen_inclusion_cmp(fc_boundary, fc_query, fc_opr_codenum) == 0)
	{
		int			fc_min_bits,
					fc_decisive_bits;

		fc_min_bits = Min(ip_bits(fc_boundary), ip_bits(fc_query));

		/*
		 * 将 decisive_bits 设置为应根据操作符包含
		 * 另一个的掩码长度。
		 */
		if (fc_opr_codenum < 0)
			fc_decisive_bits = ip_bits(fc_boundary);
		else if (fc_opr_codenum > 0)
			fc_decisive_bits = ip_bits(fc_query);
		else
			fc_decisive_bits = fc_min_bits;

		/*
		 * 现在返回非公共决定性位的数量。如果边界和查询实际上匹配，则为零，否则为正值。
		 */
		if (fc_min_bits > 0)
			return fc_decisive_bits - bitncommon(ip_addr(fc_boundary),
											  ip_addr(fc_query),
											  fc_min_bits);
		return fc_decisive_bits;
	}

	return -1;
}
